01｜复杂度直觉

对应课程：lessons/01-complexity-and-binary-search/00-time-space-and-big-o.md

课件预览

新窗口打开 / 下载

一、复杂度分析与估算

$$1sec={10}^{8}ops$$

保守估计：C++1秒处理一亿次简单运算

• 10^7:非常稳
• 10^8:有点危险，常数小能过
• 10^9:几乎必挂，除非是极简单的位运算

数据范围与算法映射表

N	时间复杂度	对应算法
<=20	$O(2^N\ast N)$	状态压缩DP
	$O(N!)$	全排列枚举
<=400	$O(N^3)$	Floyd,区间DP
<=5000	$O(N^2)$	简单DP,全对全遍历
10^5~2*10^5	$O(NlogN)$	排序，二分，堆，线段树
>10^9	$O(logN)$	快速幂
	$O(sqrtN)$	数论分解
图论(V,E)~10^5	$O(ElogV)$	Dijkstra

空间复杂度陷阱

int dp[10000][10000] = 10^8 ints

• 10^8 * 4 Bytes = 400MB。
• 题目限制 256MB -> MLE (Memory Limit Exceeded)!

递归深度 (Recursion Depth)：

• DFS最坏情况深度等于 N。
• N=10^5 时，栈内存可能溢出 (Stack Overflow)。

第二部分：二分查找(Binary Search)

二分查找的本质

• 误区：二分就是在一个有序数组中找一个数

• 正解：二分是在一个单调的空间里，寻找红蓝边界。

• 模型： [不满足,...,不满足,满足,...,满足]

• 任务：找到第一个True或最后一个False

惨痛教训：死循环

二分只有两行代码，但有大坑：

mid=(l+r)/2;
if (check(mid)) l=mid;
else r=mid;

如果l=4,r=5,mid=4 如果走l=mid分支 -> l=4 -> 死循环（TLE）！

解决：

坚持使用一套永远收缩的模版。

模版

//Find smallest x in [l,r] such that check(x) is true
long long first_true(long long l,long long r) {
  long long ans=-1;
  while(l<r){
    long long mid=l+(r-1)/2;
    if (check(mid)){
      ans=mid;
      r=mid-1; //Try smaller (Left)
    } else {
      l=mid+1; //Need bigger (Right)
    }
  }
  return ans;
}

第三部分：二分答案(BS ON answer)

什么题用二分答案？

关键词：

• 求最小化最大值
• 求最大化最小值

如果你无法直接计算出最优解， 但是给你一个值x，你很快就能判断 “做不做得到” ，既然能判定，那就去试，用二分尝试。

总结

1. 动手写代码前，先计算复杂度，不抱侥幸心理
2. 二分查找只背一个模版，理解l和r的移动逻辑
3. 遇到求“最值”且“不好直接计算”的题，第一时间想二分答案